#include <unordered_map>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


class Solution {
private:
    int search(unordered_map<int, int>& his, int val) {
        if (his.count(val) == 1) {
            return his[val];
        }
        int next_val;
        if (val % 2 == 1) {
            next_val = val * 3 + 1;
        } else {
            next_val = val / 2;
        }
        int count = 1 + search(his, next_val);
        his[val] = count;
        return count;
    }
public:
    int getKth(int lo, int hi, int k) {
        unordered_map<int, int> his;
        his[1] = 0;
        vector<pair<int, int>> set;
        for (int i = lo; i <= hi; i++) {
            int val = search(his, i);
            set.push_back({i, val});
        }
        sort(set.begin(), set.end(), [] (pair<int, int>& a, pair<int, int>& b) {
            return a.second < b.second;
        });
        return set[k - 1].first;
    }
};

int main() {
    Solution solution;
    solution.getKth(12, 15, 2);
    return 0;
}